package com.zjsru.plan2023.oneday;

import java.util.PriorityQueue;

/**
 * @Author: CookLee
 * @Date: 2023/7/25
 * 将数组和减半的最少操作次数
 * \
 * 输入：nums = [5,19,8,1]
 * 输出：3
 * 解释：初始 nums 的和为 5 + 19 + 8 + 1 = 33 。
 * 以下是将数组和减少至少一半的一种方法：
 * 选择数字 19 并减小为 9.5 。
 * 选择数字 9.5 并减小为 4.75 。
 * 选择数字 8 并减小为 4 。
 * 最终数组为 [5, 4.75, 4, 1] ，和为 5 + 4.75 + 4 + 1 = 14.75 。
 * nums 的和减小了 33 - 14.75 = 18.25 ，减小的部分超过了初始数组和的一半，18.25 >= 33/2 = 16.5 。
 * 我们需要 3 个操作实现题目要求，所以返回 3 。
 * 可以证明，无法通过少于 3 个操作使数组和减少至少一半。
 */
public class HalveArray {
    
    /**
     * 贪心+队列
     *
     * @param nums 数组
     * @return int
     */
    public int halveArray(int[] nums) {
        PriorityQueue<Double> queue = new PriorityQueue<>((a, b) -> b.compareTo(a));
        for (int num : nums) {
            queue.offer((double) num);
        }
        //定义正常相加的和
        double sum = 0.0;
        for (int num : nums) {
            sum += num;
        }
        //定义取数减半后的和
        double sum2 = 0.0;
        //定义操作数
        int count = 0;
        while (sum2 < sum / 2) {
            Double number = queue.poll();
            sum2 += number / 2;
            queue.offer(number / 2);
            count++;
        }
        return count;
    }
    
    public static void main(String[] args) {
        HalveArray halveArray = new HalveArray();
        int[] nums = new int[]{5,19,8,1};
        System.out.println(halveArray.halveArray(nums));
    }

}
